//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 10⁴ 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 👍 1510 👎 0

package leetcode.editor.cn;

import java.util.Stack;

public class _32_LongestValidParentheses {
    public static void main(String[] args) {
        String str = "(()";
        Solution solution = new _32_LongestValidParentheses().new Solution();
        int i = solution.longestValidParentheses(str);
        System.out.println(i);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 正向逆向结合法
         * @param s
         * @return
         */
        public int longestValidParentheses(String s) {
            int maxLen = 0;
            int left = 0;
            int right = 0;
            // 正向遍历
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxLen = Math.max(maxLen, left * 2);
                } else if (right > left) {
                    left = 0;
                    right = 0;
                }
            }
            // 反向遍历
            left = 0;
            right = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                if (s.charAt(i) == '(') {
                    left++;
                } else {
                    right++;
                }
                if (left == right) {
                    maxLen = Math.max(maxLen, left * 2);
                } else if (right < left) {
                    left = 0;
                    right = 0;
                }
            }

            return maxLen;
        }
        /**
         * 动态规划
         * @param s
         * @return
         */
        public int longestValidParentheses_dp(String s) {
            int maxLen = 0;
            int[] dp = new int[s.length()];
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == ')') {
                    if (s.charAt(i - 1) == '(') {
                        dp[i] = 2 + (i <= 1 ? 0 : dp[i - 2]);
                    } else if (i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {
                        dp[i] = 2 + dp[i-1] + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0);
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
            return maxLen;
        }

        /**
         * 栈
         * @param s
         * @return
         */
        public int longestValidParentheses_2(String s) {
            Stack<Integer> stack = new Stack<Integer>();
            int maxLen = 0;
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.push(i);
                } else {
                    stack.pop();
                    if (stack.empty()) {
                        stack.push(i);
                    } else {
                        maxLen = Math.max(i - stack.peek(), maxLen);
                    }
                }
            }
            return maxLen;
        }
        /**
         * 这个有问题，错了，不能处理连续情况
         * @param s
         * @return
         */
        public int longestValidParentheses_e(String s) {
            Stack<Character> stack = new Stack<Character>();
            int res = 0;
            int count = 0;
            for (char ch : s.toCharArray()) {
                if (ch == '(') {
                    stack.push(ch);
                } else {
                    if (!stack.empty()) {
                        Character peek = stack.peek();
                        if (peek == '(') {
                            stack.pop();
                            count++;
                            continue;
                        }
                        stack.push(ch);
                    }
                }
            }
            return count * 2;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}